package SlidingWindow;

import java.util.*;

/**
 * Description: 滑动窗口算法
 * User:岁亮亮
 * Date:2025-04-08
 * TIME:10:13
 */
public class Day0408 {

    //水果成蓝
    //给你一个整数数组 fruits ，返回你可以收集的水果的 最大数目。
    //其中 fruits[i] 是第 i 棵树上的水果 种类 。
    public int totalFruit(int[] fruits) {

        int left = 0, right = 0, n = fruits.length, ret = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (; right < n; right++) {
            //进窗口 并将其同种类型的水果数量加1
            map.put(fruits[right], map.getOrDefault(fruits[right], 0) + 1);
            //判断 水果种类是否超过2
            while (map.size() > 2) {
                int in = fruits[left];
                //出窗口 通过出窗口找到要删去的水果种类
                map.put(fruits[left], map.get(fruits[left]) - 1);
                if (map.get(fruits[left]) == 0) map.remove(fruits[left]);
                left++;
            }
            //更新结果
            ret = Math.max(ret, right - left + 1);
        }
        return ret;
    }

    //不借用hashMap实现
    public int totalFruit2(int[] fruits) {
        int left = 0, right = 0, n = fruits.length, ret = 0;
        //不借用hashMap
        int[] map = new int[n + 1];
        int kinds = 0;
        for (; right < n; right++) {
            //进窗口 并将其同种类型的水果数量加1
            if (map[fruits[right]] == 0)
                kinds++;
            map[fruits[right]]++;
            //判断 水果种类是否超过2
            while (kinds > 2) {
                int in = fruits[left];
                //出窗口 通过出窗口找到要删去的水果种类
                map[in]--;
                if (map[in] == 0)
                    kinds--;
                left++;
            }
            //更新结果
            ret = Math.max(ret, right - left + 1);
        }
        return ret;

    }
    //给你一个整数数组 nums 和一个整数 x 。
    // 每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值
    //如果可以将 x 恰好 减到 0 ，返回 最小操作数
    public int minOperations(int[] nums, int x) {

        int left = 0,right = 0,n = nums.length,ret = 0;
        //找出 和位sum - x 最长子数组
        for(int i = 0; i < n; i++){
            ret += nums[i];
        }
        if(ret < x)return -1;
        int target = ret - x;
        ret = 0;
        int s = Integer.MIN_VALUE;
        for(; right < n;right++){
            //进窗口
            ret += nums[right];
            //判断
            while(ret > target){
                //出窗口
                ret -= nums[left++];
            }
            if(ret == target) s = Math.max(s,right - left + 1);
        }
        return s == Integer.MIN_VALUE ? -1 : n-s;

    }


}
